import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.text.ParseException;
import java.util.LinkedList;

/** 
 * De parser herkent zinnen van een simpele grammatica.
 * Deze grammatica is G(&lt;expression&gt;)<br><br>
 * &nbsp;&lt;expression&gt; ::= &lt;term&gt; &lt;expression-tail&gt;<br>
 * &nbsp;&lt;expression-tail&gt; ::= e | &lt;plus-expression&gt; | &lt;minus-term&gt;<br>
 * &nbsp;&lt;plus-expression&gt; ::= PLUS &lt;expression&gt;<br>
 * &nbsp;&lt;minus-term&gt; ::= MINUS &lt;term&gt; &lt;expression-tail&gt;<br>
 * &nbsp;&lt;term&gt; ::= &lt;factor&gt; &lt;term-tail&gt;<br>
 * &nbsp;&lt;term-tail&gt; ::= e | &lt;times-term&gt;<br>
 * &nbsp;&lt;times-term&gt; ::= TIMES &lt;term&gt;<br>
 * &nbsp;&lt;factor&gt; ::= PARENT_LEFT &lt;expression&gt; PARENT_RIGHT<br>
 * &nbsp;&lt;factor&gt; ::= ID | INT | LONG | FLOAT | DOUBLE<br>
 * [Namen in hoofdletters zijn tokens die door de scanner herkend worden.]<br>
 * Het resultaat van parsen is een string representatie van de oorspronkelijke
 * expressie met daaraan haakjes toegevoegd die de volgorde van evaluatie
 * duidelijk maakt. Bijvoorbeeld, de invoer expressie <code>1+2*3</code>
 * resulteert in <code>(1+(2*3))</code>, omdat de vermenigvuldig operator
 * sterker bindt (en dus eerder wordt ge&euml;valueerd) dan de optel operator.
 */
class Parser implements TokenKinds {

	/**
	 * De scanner die de tokens levert voor deze parser.
	 */
	private Scanner scanner;

	/**
	 * 1 lookahead voor een LL(1) parser.
	 */
	private Token lookahead;

	/**
	 * Een fout is opgetreden bij het parsen van de nonterminal.
	 * @param nonterminal naam van nonterminal
	 * @param message foutmelding
	 */
	private void parseError(String nonterminal,String message) {
		System.err.println();
		System.err.println("parse error in <"+nonterminal+"> : "+message);
		System.err.print("lookahead '"+lookahead.getText()+"' ");
		System.err.print("(kind="+lookahead.getKind()+") ");
		System.err.print("at "+lookahead.getLine()+"/"+lookahead.getColumn());
		System.err.println();
		throw new RuntimeException();
	}

	/**
	 * Accepteer huidige token van scanner.
	 */
	private void acceptIt() {
		try {
			lookahead=scanner.nextToken();
		} catch (IOException exception) {
			exception.printStackTrace();
			throw new RuntimeException();
		}
	}

	/**
	 * Accepteer huidige token van scanner, mits deze van een bepaald soort is.
	 * @param nonterminal naam van nonterminal
	 * @param kind identifatie van token soort
	 */
	private void accept(String nonterminal,int kind) {
		if ( lookahead.getKind()!=kind ) {
			parseError(nonterminal,"kind="+kind+" expected");
		} else {
			acceptIt();
		}

	}

	/**
	 * Construeer een nieuwe parser op de input stream.
	 * @param in input stream van characters
	 */
	public Parser(InputStream in) {
		scanner=new Scanner(new BufferedReader(new InputStreamReader(in)));
		//Initialiseer lookahead met eerste token van scanner
		acceptIt();
	}

	/**
	 * Parse het root symbool van de grammatica.
	 * @return het resultaat van parsing (in dit geval een string)
	 */
	public Object parseRoot() {
		parseBnf();
		//Na parsen van root symbol moet EOF token gescanned worden
		accept("root",EOF);
		//Geef de root van de opgebouwde expressie stack terug
		return pop();
	}

	/**
	 * Een interne stack om string representatie van expressie te kunnen bouwen.
	 */
	private LinkedList expressionStack=new LinkedList();

	/**
	 * Push (tekst van) current token op de interne stack.
	 */
	private void pushIt() {
		push(lookahead.getText());
	}

	/**
	 * Push een object op de interne stack.
	 * @param object object dat bovenop de stapel wordt geplaatst
	 */
	private void push(Object object) {
		expressionStack.addFirst(object);
	}

	/**
	 * Haal bovenste object van de interne stack.
	 * @return bovenste verwijderde element
	 */
	private Object pop() {
		return expressionStack.removeFirst();
	}

	private void parseBnf() {
		parseRule();
		parseRestRules();
	}

	private void parseRule() {
		accept("NonTerminal", NONTERMINAL);
		accept("isDefinedAs", IS_DEFINED_AS);
		parseAlternatives();

	}	
	
	private void parseAlternatives() {
		parseOneAlternative();
		parseOtherAlternative();		
	}

	

	private void parseOneAlternative() {
		switch (lookahead.getKind() ) {
		case EMPTY:
			accept("EMPTY", EMPTY);
			break;
		
		case NONTERMINAL:
		case TERMINAL:
			parseTerm();
			parseRestAlternative();
			break;
		default: 
			parseError("niets", "dat kan niet!!!");
		}
	}

	
	private void parseOtherAlternative() {		
		switch (lookahead.getKind() ) {
		case OR:
			accept("|", OR);
			parseAlternatives();
			break;
		case EMPTY:
			accept("Empty", EMPTY);
		default: ;
		}
		
	}
	
	private void parseRestRules() {
		 switch (lookahead.getKind() ) {
		case NONTERMINAL:
			parseBnf();			
			break;
		case EMPTY:
			accept("Empty", EMPTY);
		default: ;
		}
	}	

	private void parseRestAlternative() {
		switch (lookahead.getKind()) {
		case TERMINAL:
		case NONTERMINAL:
			parseTerm();
			parseRestAlternative();
			accept("EOL", EOL);
			break;		
		default:
			;
		}
		
	}

	private void parseTerm() {
		switch (lookahead.getKind() ) {
		case TERMINAL:
			accept("Terminal", TERMINAL);
			break;
		case NONTERMINAL:
			accept("NonTerminal", NONTERMINAL);
			break;
		default: ;
		}
		
	}


	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;expression&gt; ::= &lt;term&gt; &lt;expression-tail&gt;
	//   */
	//  private void parseExpression() {
	//    parseTerm();
	//    parseExpressionTail();
	//  }
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;expression-tail&gt; ::= e | &lt;plus-expression&gt; | &lt;minus-term&gt;
	//   */
	//  private void parseExpressionTail() {
	//    switch (lookahead.getKind() ) {
	//      case PLUS:
	//        parsePlusExpression();
	//        break;
	//      case MINUS:
	//        parseMinusTerm();
	//        break;
	//    }
	//  }
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;plus-expression&gt; ::= PLUS &lt;expression&gt;
	//   */
	//  private void parsePlusExpression()  {
	//    accept("plus-expression",PLUS);
	//    parseExpression();
	//    Object right=pop(), left=pop();
	//    push("("+left+"+"+right+")");
	//  }
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;minus-term&gt; ::= MINUS &lt;term&gt; &lt;expression-tail&gt;
	//   */
	//  private void parseMinusTerm() {
	//    accept("minus-term",MINUS);
	//    parseTerm();
	//    Object right=pop(), left=pop();
	//    push("("+left+"-"+right+")");
	//    parseExpressionTail();
	//  } 
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;term&gt; ::= &lt;factor&gt; &lt;term-tail&gt;
	//   */
	//  private void parseTerm() {
	//    parseFactor();
	//    parseTermTail();
	//  }
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;term-tail&gt; ::= e | &lt;times-term&gt;
	//   */
	//  private void parseTermTail() {
	//    switch (lookahead.getKind() ) {
	//      case TIMES:
	//        parseTimesTerm();
	//        break;
	//    }
	//  }
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;times-term&gt; ::= TIMES &lt;term&gt;
	//   */
	//  private void parseTimesTerm() {
	//    accept("times-term",TIMES);
	//    parseTerm();
	//    Object right=pop(), left=pop();
	//    push("("+left+"*"+right+")");
	//  } 
	//
	//  /**
	//   * Parsen van<br>
	//   * &nbsp;&lt;factor&gt; ::= PARENT_LEFT &lt;expression&gt; PARENT_RIGHT
	//   * &nbsp;&lt;factor&gt; ::= ID | INT | LONG | FLOAT | DOUBLE<br>
	//   */
	//  private void parseFactor() {
	//    switch (lookahead.getKind()) {
	//      case PARENT_LEFT:
	//        acceptIt();
	//        parseExpression();
	//        accept("factor",PARENT_RIGHT);
	//        break;
	//      case ID:
	//      case INT:
	//      case LONG:
	//      case FLOAT:
	//      case DOUBLE:
	//        pushIt();
	//        acceptIt();
	//        break;
	//      default:
	//        parseError("factor","lookahead unexpected");
	//    }
	//  }

}
